//给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。 
//
// 返回执行此操作后，grid 中最大的岛屿面积是多少？ 
//
// 岛屿 由一组上、下、左、右四个方向相连的 1 形成。 
//
// 
//
// 示例 1: 
//
// 
//输入: grid = [[1, 0], [0, 1]]
//输出: 3
//解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。
// 
//
// 示例 2: 
//
// 
//输入: grid = [[1, 1], [1, 0]]
//输出: 4
//解释: 将一格0变成1，岛屿的面积扩大为 4。 
//
// 示例 3: 
//
// 
//输入: grid = [[1, 1], [1, 1]]
//输出: 4
//解释: 没有0可以让我们变成1，面积依然为 4。 
//
// 
//
// 提示： 
//
// 
// n == grid.length 
// n == grid[i].length 
// 1 <= n <= 500 
// grid[i][j] 为 0 或 1 
// 
// Related Topics深度优先搜索 | 广度优先搜索 | 并查集 | 数组 | 矩阵 
//
// 👍 197, 👎 0 
//
//
//
//

package leetcode.editor.day;

import java.util.*;

// 827. 最大人工岛
// https://leetcode.cn/problems/making-a-large-island/solution/zui-da-ren-gong-dao-by-leetcode-solution-lehy/
class MakingALargeIsland {
    public static void main(String[] args) {
        Solution solution = new MakingALargeIsland().new Solution();
        solution.largestIsland(new int[][]{{1, 1}, {1, 0}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int m, n;

        // DFS : https://leetcode.cn/problems/making-a-large-island/solution/zui-da-ren-gong-dao-by-leetcode-solution-lehy/
        // TODO 并查集
        public int largestIsland(int[][] grid) {
            this.m = grid.length;
            this.n = grid[0].length;
            int[][] tag = new int[m][n];    // 保存编号的矩阵
            Map<Integer, Integer> area = new HashMap<>();
            int res = 0;

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 注意搜索所有岛屿保存在map中
                    if (grid[i][j] == 1 && tag[i][j] == 0) {
                        int t = i * m + j + 1;  // 编号
                        int size = dfs(grid, i, j, tag, t);
                        area.put(t, size);   // 记录编号对应的面积大小
                        // 记录最大的岛屿面积
                        res = Math.max(res, size);
                    }
                }
            }

            int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 此时再搜索0，搜索上下左右是否有岛屿，有就能连起来，求面积总和
                    if (grid[i][j] == 0) {
                        // 使用hash去重,左右都是一个岛屿，就不用加2次
                        Set<Integer> set = new HashSet<>();
                        int size = 1;
                        for (int[] dir : dirs) {
                            int x = i + dir[0];
                            int y = j + dir[1];
                            // 越界、去重、没有岛屿都不符合
                            if (x < 0 || y < 0 || x >= m || y >= n || set.contains(tag[x][y]) || tag[x][y] == 0)
                                continue;
                            // 获取岛屿面积
                            size += area.get(tag[x][y]);
                            set.add(tag[x][y]);
                        }
                        res = Math.max(res, size);
                    }
                }
            }

            return res;
        }


        public int dfs(int[][] grid, int i, int j, int[][] tag, int t) {
            if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0 || tag[i][j] != 0) return 0;
            tag[i][j] = t;
            return dfs(grid, i - 1, j, tag, t) + dfs(grid, i + 1, j, tag, t) + dfs(grid, i, j - 1, tag, t) + dfs(grid, i, j + 1, tag, t) + 1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
